//
//  5. 最长回文子串.swift
//  手撕代码
//
//  Created by xiaoZuDeMeng on 2024/2/22.
//

import Foundation

//给你一个字符串 s，找到 s 中最长的回文子串。
//
//如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
//
//
//
//示例 1：
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//示例 2：
//
//输入：s = "cbbd"
//输出："bb"
//
//
//提示：
//
//1 <= s.length <= 1000
//s 仅由数字和英文字母组成


//思路
//
//从每一个位置出发，向两边扩散，检查是否为回文串。
//
//算法
//
//定义start和end指针，表示找到的最长回文串。
//回文串长度可以为奇数奇数或偶数，两种情况的回文中心不同，所以两种情况都做遍历。
//当回文串为奇数时，以一个元素i为中心，向两边扩散。
//当回文串为偶数时，以i和i+1两个元素为中心，向两边扩散。
//
//expandAroundCenter函数用来查找回文串。
//定义left和right，表示左右扩展的边界。比较left和right的元素是否相同，如果相同则继续扩展，用区间[left,right]表示当前找到的回文串。

func longestPalindrome(_ s: String) -> String {
    let chars = Array(s)
    var start = 0, end = 0
    for i in 0..<chars.count {
        let len1 = expandAroundCenter(chars, i, i)
        let len2 = expandAroundCenter(chars, i, i + 1)
        let len = max(len1, len2)
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return String(chars[start..<end + 1])
}

func expandAroundCenter(_ chars: [Character], _ left: Int, _ right: Int) -> Int {
    var left = left
    var right = right
    while left >= 0 && right < chars.count {
        if chars[left] != chars[right] {
            break
        }
        left -= 1
        right += 1
    }
    return right - left - 1
}

